﻿#include<iostream>
#include<fstream>
#include <io.h>
#include<algorithm>
#include <cmath>
#include "AVLTree.h"
using namespace std;

//单词的加载 即构造函数 放入到AVL树中
AVLTree::AVLTree() {
	int i;
	WordEnter();//将单词从文件中读入到程序的数组中存储
	First_Insert();//将单词从数组中写入到AVL树中
	cout << "单词已加载完成，欢迎使用~" << endl;
	system("pause");
}

AVLTree::~AVLTree() {//析构函数
	DeleteAVLTree(root);
}
//四种AVL旋转
AVLNode* AVLTree::RR_Rotate(AVLNode* t) {//RR_Rotate型旋转，左旋
	AVLNode* tmp;
	tmp = t->right;
	t->right = tmp->left;
	tmp->left = t;

	t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
	tmp->height = max(GetHeight(tmp->left), GetHeight(tmp->right)) + 1;

	return tmp;
}
AVLNode* AVLTree::LL_Rotate(AVLNode* t) {//LL_Rotate型旋转，右旋
	AVLNode* tmp;
	tmp = t->left;
	t->left = tmp->right;
	tmp->right = t;

	t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
	tmp->height = max(GetHeight(tmp->left), GetHeight(tmp->right)) + 1;

	return tmp;
}
AVLNode* AVLTree::LR_Rotate(AVLNode* t) {
	AVLNode* tmp;
	tmp = t->left;
	t->left = RR_Rotate(tmp);
	return LL_Rotate(t);
}
AVLNode* AVLTree::RL_Rotate(AVLNode* t) {
	AVLNode* tmp;
	tmp = t->right;
	t->right = LL_Rotate(tmp);
	return RR_Rotate(t);
}

//获取一颗树的高度
int AVLTree::GetHeight(AVLNode* t) {
	return (t == NULL) ? 0 : (t->height);
}

//设置一个结点的高度
void AVLTree::SetHeight(AVLNode* t, int height) {
	t->height = height;
}

//插入一个结点
AVLNode* AVLTree::Insert(AVLNode* t, string eng, string chi) {
	if (t == NULL) {	//插入一个新的叶子节点
		t = new AVLNode;
		t->word = eng;
		t->mean = chi;
		t->height = 1;
		t->left = NULL;
		t->right = NULL;
	}
	else if (eng < t->word) {	//如果要插入的单词小于当前节点的单词，就应该插入到该单词的左子树上，再进行递归
		t->left = Insert(t->left, eng, chi);
		if (GetHeight(t->left) - GetHeight(t->right) > 1) { //AVL树不平衡，需要进行调整
			if (eng < t->left->word) {	//判断进行何种旋转
				t = LL_Rotate(t);
			}
			else {
				t = LR_Rotate(t);
			}
		}
	}
	else if (eng > t->word) { //如果要插入的单词大于当前节点的单词，就应该插入到该单词的右子树上，再进行递归
		t->right = Insert(t->right, eng, chi);
		if (GetHeight(t->right) - GetHeight(t->left) > 1) { //AVL树不平衡，需要进行调整
			if (eng > t->right->word) { //判断进行何种旋转
				t = RR_Rotate(t);
			}
			else {
				t = RL_Rotate(t);
			}
		}
	}
	SetHeight(t, max(GetHeight(t->left), GetHeight(t->right)) + 1);//重新设置高度
	return t;
}

/*查找单词内部接口实现,返回一个结点，该节点即要查找到的结点，
  如果该节点为空，即没有找到该结点，就返回一个空的结点
*/
AVLNode* AVLTree::FindWord(AVLNode* t, string eng) {
	if (t == NULL) {
		return NULL;
	}
	if (eng == t->word) {
		return t;
	}
	else if (eng > t->word) {
		return FindWord(t->right, eng);
	}
	else {
		return FindWord(t->left, eng);
	}
}

/*删除一个单词*/
AVLNode* AVLTree::Delete(AVLNode* t, string eng) {
	AVLNode* oldNode = NULL;
	if (eng == t->word) { //要删除的节点是根节点
		if (t->left != NULL && t->right != NULL) {
			if (GetHeight(t->left) > GetHeight(t->right)) {
				//左子树高度大，删除左子树中元素值最大的那个节点，同时将其值赋值给根节点
				t->word = GetMaxNode(t->left)->word;//以左子树的最大值替换当前值
				t->mean = GetMaxNode(t->left)->mean;//以左子树的最大值替换当前值
				t->left = Delete(t->left, t->word);//删除左子树中已经替换上去的节点
			}
			else {
				//删除右子树中元素值最小的那个节点，同时将其值赋值给根节点
				t->word = GetMinNode(t->right)->word;//以右子树的最大值替换当前值
				t->mean = GetMaxNode(t->right)->mean;//以右子树的最大值替换当前值
				t->right = Delete(t->right, t->word);//删除右子树中已经替换上去的节点
			}
		}
		else {
			//左右子树中有一个不为空，那个直接用需要被删除的节点的子节点替换之即可
			oldNode = t;
			t = (t->left ? t->left : t->right);
			delete oldNode;
			oldNode = NULL;
		}
	}
	else if (eng < t->word) { //要删除的节点在左子树中
		t->left = Delete(t->left, eng);
		//判断是否仍然满足平衡条件
		if (GetHeight(t->right) - GetHeight(t->left) > 1) {
			if (GetHeight(t->right->left) > GetHeight(t->right->right)) {
				t = RL_Rotate(t);
			}
			else {
				t = RR_Rotate(t);
			}
		}
		else {
			t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
		}
	}
	else { //需要删除的节点在右子树中
		t->right = Delete(t->right, eng);
		if (GetHeight(t->left) - GetHeight(t->right) > 1) {
			if (GetHeight(t->left->right) > GetHeight(t->left->left)) {
				t = LR_Rotate(t);
			}
			else {
				t = LL_Rotate(t);
			}
		}
	}
	return t;
}


//中序遍历AVL树
void AVLTree::InOrder(AVLNode* t) {
	if (t == NULL) {
		return;
	}
	else {
		InOrder(t->left);
		cout << t->word << " " << t->mean << " " << endl;
		InOrder(t->right);
	}
}

//将更新完毕后的单词输入到对应文件当中
void AVLTree::Update(int count) {
	int front = -1;
	int rear = -1;
	int length = 0;
	int i;
	AVLNode* q = NULL;
	AVLNode* Q[10000];
	string M[10000];
	char filename[26][100] = {"C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\a.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\b.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\c.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\d.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\e.txt",
							  "C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\f.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\g.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\h.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\i.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\j.txt",
							  "C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\k.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\l.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\m.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\n.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\o.txt",
							  "C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\p.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\q.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\r.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\s.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\t.txt",
							  "C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\u.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\v.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\w.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\x.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\y.txt",
							  "C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\z.txt"
	};
	ofstream out(filename[count]);
	//这里打算用层序遍历的思想，找到开头对应的单词写入文件中，即文件的更新
	if (root == NULL) {
		return;
	}
	Q[++rear] = root;
	while (front != rear) {
		q = Q[++front];
		if (out.is_open()) {
			if ((int)q->word[0] - 97 == count) {
				//				out << q->mean << "\n";
				//				cout << q->mean << "成功写入文件!" << endl;
				M[length++] = q->mean;
			}
		}
		if (q->left != NULL) {
			Q[++rear] = q->left;
		}
		if (q->right != NULL) {
			Q[++rear] = q->right;
		}
	}
	sort(M, M + length);//排序函数
	for (i = 0; i < length; i++) {
		out << M[i] << "\n";//依次写入对应文件中
	}
	out.close();
}
void AVLTree::WordEnter() {//文件录入函数
	char filename[26][100] = {"C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\a.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\b.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\c.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\d.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\e.txt",
							  "C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\f.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\g.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\h.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\i.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\j.txt",
							  "C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\k.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\l.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\m.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\n.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\o.txt",
							  "C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\p.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\q.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\r.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\s.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\t.txt",
							  "C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\u.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\v.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\w.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\x.txt","C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\y.txt",
							  "C:\\Users\\ALIENWARE\\Desktop\\QT\\word\\z.txt"
	};
	int i;
	int j;
	int k;
	int count = 0;
	char buffer[300];
	char eng[200];
	ifstream file;
	//新加入：
	word_length[0] = 0;
	for (k = 0; k < 26; k++) {
		file.open(filename[k]);
		if (!file.is_open()) {
			cout << "Error opening file" << endl;
			exit(1);
		}
		while (!file.eof()) {
			file.getline(buffer, 100);
			for (i = 0; buffer[i] != '\0'; i++) {
				if (buffer[i] == ' ') {
					for (j = 0; j < i; j++) {
						eng[j] = buffer[j];
					}
					break;
				}
			}
			word[count] = eng;
			mean[count] = buffer;
			count++;
			memset(eng, '\0', sizeof(eng));//清空这个eng[]数组，以便下次继续调用
		}
		//新修改：
		word_length[k + 1] = count;
		//				cout << word_length[k+1] << endl;
		file.close();
	}
	length = count;
	//			cout << "长度：" << length << endl;
	//			cout << "文件已全部加载完成，祝您使用愉快~" << endl;
	//			system("pause");
}
void AVLTree::InOrder() {//中序遍历
	InOrder(root);
}

//单词查找函数外部接口
void AVLTree::FindWord() {
	AVLNode* p = NULL;
	string eng;
	cout << "请输入您想查找的单词：";
	cin >> eng;
	p = FindWord(root, eng);
	if (p == NULL) {
		cout << "并没有这个单词~" << endl;
		system("pause");
	}
	else {
		cout << "该单词的意思为：" << endl;
		cout << p->mean << endl;
		system("pause");
	}
}

//这个函数是用来将单词从文件中读入到程序的数组中存储（程序自动录入已有单词时） 
void AVLTree::First_Insert() {
	int i;
	for (i = 0; i < length; i++) {
		root = Insert(root, word[i], mean[i]);
		//				cout << "正在加载第" << i <<"个单词" <<endl;
	}
}
//这个函数是用来将单词从程序中写入到AVL树中(用户输入单词时)
void AVLTree::Second_Insert() {
	string eng;
	string chi;
	AVLNode* p = NULL;
	cout << "请输入您想插入的单词: ";
	cin >> eng;
	//这一部分是用来查找是否该单词已经存在了
	p = FindWord(root, eng);
	if (p == NULL) {
		//				cout << "并没有这个单词~" << endl;
		cout << "请输入这个单词的中文意思: ";
		cin >> chi;
		chi = eng + "   " + chi;//统一格式
		//插入这个单词
		root = Insert(root, eng, chi);
		Update((int)eng[0] - 97);//文件更新 
		cout << "插入完成~" << endl;
		system("pause");
	}
	else {
		cout << "该单词已经存在了，请勿重复添加哦" << endl;
		system("pause");
		return;
	}
}
//这个函数是用来删除某一单词的
void AVLTree::DeleteWord() {
	AVLNode* p = NULL;
	string eng;
	cout << "请输入您想删除的单词：";
	cin >> eng;
	p = FindWord(root, eng);
	if (p == NULL) {
		cout << "抱歉，该词典中并没有您想删除的这个单词哦~" << endl;
		system("pause");
		return;
	}
	else {
		root = Delete(root, eng);
		Update((int)eng[0] - 97);//文件更新 
		cout << "该单词已删除完毕~" << endl;
		system("pause");
		return;
	}
}
//AVL树析构时需要调用的函数 
void AVLTree::DeleteAVLTree(AVLNode* p) {
	if (p == NULL) {
		return;
	}
	else {
		DeleteAVLTree(p->left);
		DeleteAVLTree(p->right);
		delete p;
	}
}
//删除单词函数中所需要用到的函数
//1 找到最大的节点
AVLNode* AVLTree::GetMaxNode(AVLNode* t) {
	AVLNode* p = NULL;
	if (t == NULL) {
		return NULL;
	}
	p = t;
	while (p->right) {
		p = p->right;
	}
	return p;
}
//2 找到最小的节点
AVLNode* AVLTree::GetMinNode(AVLNode* t) {
	AVLNode* p = NULL;
	if (t == NULL) {
		return NULL;
	}
	p = t;
	while (p->left) {
		p = p->left;
	}
	return p;
}
//功能表一览
void AVLTree::StartShow() {
	system("cls");
	cout << "                     |=======================|" << endl;
	cout << "                     |欢迎使用本英汉双解词典~|" << endl;
	cout << "                     |                       |" << endl;
	cout << "                     |                       |" << endl;
	cout << "                     |      使用说明：       |" << endl;
	cout << "                     |     1:查找单词：      |" << endl;
	cout << "                     |     2:插入单词:       |" << endl;
	cout << "                     |     3:删除单词:       |" << endl;
	cout << "                     |   4:显示所有单词：    |" << endl;
	cout << "                     |       5:退出          |" << endl;
	cout << "                     |                       |" << endl;
	cout << "                     |                       |" << endl;
	cout << "                     |=======================|" << endl;
	cout << "                     |请选择你想进行的操作： |" << endl;
}